// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），
// 可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。


// 空间复杂度要求O(1) --> 不能用哈希
// 时间复杂度要求O(n^2) --> 不能暴力
// 不修改数组 --> 不能排序，不能用对号入座（缺失的第一个正数）

// 对值域二分, 时间复杂度为N*log(N)
int findDuplicate(int* nums, int numsSize){
    int l = 1, r = numsSize - 1;   // 数值范围为[1, r]
    while (l < r) {
        int m = l + (r - l)/2;

        // 统计[1, m]范围内数值的个数，如果没有重复则[1, m]范围对应的坑位为m个
        int cnt = 0;
        for (int i = 0; i < numsSize; i++)
            if (nums[i] <= m) cnt++;
        
        if (cnt > m) r = m;   // 个数超过m，则重复元素在[l, m]中
        else l = m+1; // 否则在[m+1, r]中
    }
    return l;
}   